package Leetcode;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value)如果关键字key 已经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */
public class 力扣146_LRU缓存 {

    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2(2);
        cache.put(1, 1);
        cache.put(2, 2);
        int i = cache.get(1);
        cache.put(3, 3);
        int i1 = cache.get(2);
        cache.put(4, 4);
        int i2 = cache.get(1);
        int i3 = cache.get(3);
        int i4 = cache.get(4);
        System.out.println();
    }

    // 基于LinkedHashMap修改
    private static class LRUCache extends LinkedHashMap<Integer, Integer> {
        int cap = 0;

        public LRUCache(int capacity) {
            super(capacity, 1, true);
            this.cap = capacity;
        }

        public int get(int key) {
            return super.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return this.size() > this.cap;
        }
    }


    /**
     * 自定义双向链表记录插入顺序
     */
    private static class LRUCache2 {
        HashMap<Integer, SubNode> map;
        int cap;
        SubNode head;
        SubNode tail;

        public LRUCache2(int cap) {
            this.cap = cap;
            map = new HashMap<>(cap);
            head = new SubNode();
            tail = new SubNode();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            SubNode subNode = map.get(key);
            if (subNode != null) {
                moveHead(subNode);
                return subNode.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            SubNode node = map.get(key);
            if (node == null) {
                node = new SubNode();
                node.key = key;
                node.value = value;
                addNode(node);
                map.put(key, node);
                if (map.size() > cap) {
                    map.remove(removeLast());
                }
            } else {
                node.value = value;
                moveHead(node);
            }
        }

        private void moveHead(SubNode node) {
            remove(node);
            addNode(node);
        }

        private void remove(SubNode node) {
            // 从当前位置删除
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        private void addNode(SubNode node) {
            // 移到首位
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }

        private int removeLast() {
            SubNode node = tail.pre;
            remove(node);
            return node.key;
        }
    }


    private static class SubNode {
        int key;
        int value;
        SubNode pre;
        SubNode next;

        public SubNode() {
        }
    }

}
